package Array;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 88. Merge Sorted Array（合并两个有序数组）
 * https://leetcode.com/problems/merge-sorted-array/description/
 *
 * Given two sorted integer arrays nums1 and nums2,
 * merge nums2 into nums1 as one sorted array.
 *
 * Note:
 *
 * The number of elements initialized in nums1 and nums2 are m and n respectively(分别).
 * You may assume that nums1 has enough space (size that is greater or equal to m + n)
 * to hold(保存) additional elements from nums2.
 *
 * Example:
 *
 * Input:
 * nums1 = [1,2,3,0,0,0], m = 3
 * nums2 = [2,5,6],       n = 3
 *
 * Output: [1,2,2,3,5,6]
 */
public class E_088_合并两个有序数组 {

    /**
     * 不推荐
     * 将nums2放到nums1的后面，然后进行排序
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m+i] = nums2[i];
        }

        Arrays.sort(nums1);
    }

    /**
     * 从后往前比，进行添加
     */
    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return;
        int maxLength = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            if (nums1[m] > nums2[n]) {
                nums1[maxLength--] = nums1[m--];
            } else {
                nums1[maxLength--] = nums2[n--];
            }
        }
        while (n >= 0) {
            nums1[maxLength--] = nums2[n--];
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};
        int[] nums2 = {2,5,6};
        merge2(nums1,3,nums2,3);
        System.out.println(Arrays.toString(nums1));
    }
}
